前言：

程式碼（program code）儲存在硬碟（Hard Disk Memory），當啟動執行檔執行命令的時候，執行檔在隨機存取記憶體（RAM）形成一個進程（process），當 CPU 需要時，呼叫各個命令（instruction）完成指令。進程(process)是指一個正在執行的程式，當程式要求被執行時，就會被載入到記憶體中，形成一個進程。在進程中，包括了程式碼、資料和堆疊等。

可能的問題

當Process總大小超過RAM時

在一個系統中，RAM的大小是有限的，而program code的大小是不限的。當process的大小超過RAM的大小時，或是多個process同時需要被執行，就會出現系統會因為無法分配更多的 RAM 而無法執行程式

記憶體碎片化導致沒有完整的區段可以執行指令的時候

因為記憶體碎片化（Memory Fragmentation）導致沒有完整的區段可以執行指令，這樣 CPU 在執行指令時，就會因為找不到足夠的記憶體而停止執行。

Virtual Memory實現

為了解決記憶體碎片化的問題，現在的系統都會做記憶體虛擬化（Memory Virtualization），也就是給每一個進程（Process）一個完整的虛擬記憶體（Virtual Memory），需要載下來時再對應到實體記憶體（Physical Memory）。
Virtual Memory 可以將碎片化的區塊結合成完整的一片給進程（Process）使用，讓每一個進程（Process）在執行時都以為得到的是一整塊完整的記憶體區塊，但實際上可能是碎片化的。

此外，Virtual Memory 的實現需要使用硬碟記憶體（Hard Disk Memory）作為暫存的地方。

功用

• 允許程式大小大於實體記憶體（Physical Memory），因為 Virtual Memory 可以將整個程式都載入，只有被 CPU 叫到的功能才會被送到 RAM 執行，所以看到的 Virtual Memory 往往會大於實際記憶體用量多很多。
• 每一次的 I/O transfer time 可以下降，因為不用將整個程式的所有 page 載入（然而載入整個程式很耗費 I/O transfer time，因為總傳輸次數變多）。

實現

Demand Paging（Lazy Loading）

Demand Paging 策略中，程式執行之初不將全部的 pages 載入 memory，而是僅載入執行所需的 pages。如要處理 page fault 問題，由作業系統另行處理。例如，整個系統被載入 Virtual Memory，但需要執行某個 function 時，這個 function 才會從 Virtual Memory 載入到 Physical Memory。

• page fault（分頁錯誤）
  • 當有些 pages 不在 main memory 時，os必須執行page replacement。先找到一個victim page，並將其swap out到disk來空出一個free frame，再將需求page swap in 到這個frame

Copy-on-Write

在 Copy-on-Write 策略中，如果有多個呼叫者同時要求相同資源（如記憶體或磁碟上的資料儲存），則他們會共同取得相同的指標指向相同的資源，直到某個呼叫者試圖修改資源的內容時，系統才會真正複製一份專用副本（private copy）給該呼叫者，而其他呼叫者所見到的最初的資源仍然保持不變。因為沒有修改就不會產生副本，所以多用來讀多寫少的開發場景。

Page Replacement Algorithm

Page Replacement Algorithm 是一種分頁處理的演算法，用於處理 Virtual Memory 中 page 的選擇和置換。若Memory內沒有frame可以用時，可以跑可以找一個暫時不用的page，將其清除，供目前需求page使用。

常見的 Page Replacement Algorithm 包括：FIFO（First In First Out）、OPT（Optimal Algorithm）、LRU（Least Recently Used）、LFU（Least Frequently Used）等。

FIFO

當要替換一頁page時，系統就去選擇記憶體內最久的一個page，也就是最早被載入記憶體的page，將它換成需求的page。可透過FIFO queue來掌握記憶體內的所有分頁。

一共發生12次page fault
但是可能會Belady’s Anomaly問題

OPT （最佳演算法）

將長期沒用到的page換成需求page，把未來長時間不會用到的page替換掉。（首先要有預知未來的技術）

LRU

把最近不常使用的page替換掉，用過去推測未來。但需要特殊的硬體支援，很少系統能完整的實作。

• Counter：利用Counter做一個logical timer，參考page的the last reference time欄位，將來挑 the last reference time 最小的 page (離現在最久)的作為victim page
• Stack：最近的page會至於stack的top端，bottom端為離先在最久的page，會最先作為victim page換掉

LFU

最不經常使用的 (least frequently used, LFU)演算法讓次數最少的那一頁被替換掉。